/*
实验2-4 单链表分段逆转
分数 25
作者 陈越
单位 浙江大学

给定一个带头结点的单链表和一个整数 k，要求你将链表中的每 k 个结点做一次逆转。
例如给定单链表 1→2→3→4→5→6 和 k=3，你需要将链表改造成 3→2→1→6→5→4；
如果 k=4，则应该得到 4→3→2→1→5→6。
函数接口定义：

void K_Reverse( List list, int k );

其中List结构定义如下：

typedef struct ListNode *Position; /* 指针即结点位置
struct ListNode {
    ElemSet data;  /* 存储数据
    Position next;  /* 线性表中下一个元素的位置
};

typedef struct HeadNode *List;
struct HeadNode {
    Position head;  /* 单链表头指针
    int length;    /* 表长
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等；
list 是给定的带头结点的单链表，k 是每段的长度。函数 K_Reverse 应将 list
中的结点按要求分段逆转。

输入样例：

6
1 2 3 4 5 6
4

输出样例：

4 3 2 1 5 6

*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
struct ListNode {
    ElemSet data;  /* 存储数据 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *List;
struct HeadNode {
    Position head; /* 单链表头指针 */
    int length;    /* 表长 */
};

List ReadInput() { /* 读输入，创建带头结点的单链表 */
    int n, i;
    List list;
    Position tail, new_node;

    list = (List)malloc(sizeof(struct HeadNode));
    list->head = (Position)malloc(sizeof(struct ListNode)); /* 创建空头结点 */
    scanf("%d", &n);
    list->length = n;
    tail = list->head; /* 初始化尾指针 */
    for (i = 0; i < n; i++) {
        new_node = (Position)malloc(sizeof(struct ListNode));
        scanf("%d", &new_node->data);
        new_node->next = NULL;
        tail->next = new_node; /* 插入表尾 */
        tail = new_node;
    }
    return list;
}

void PrintList(List list) { /* 顺序输出链表结点数据 */
    Position p;

    p = list->head->next; /* p指向第1个结点 */
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
}

void K_Reverse(List list, int k);

int main(void) {
    List list;
    int k;

    list = ReadInput();
    scanf("%d", &k);
    K_Reverse(list, k);
    PrintList(list);

    return 0;
}
/* 你的代码将被嵌在这里 */

// 逆转链表中k个节点的函数，返回逆转后的尾结点
Position ReverseList(Position curr, int k, Position *nextPrev) {
    Position prev = NULL;
    for (int i = 0; i < k && curr != NULL; i++) {
        // *tail = curr;
        Position next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *nextPrev = curr;
    return prev;
}

void K_Reverse(List list, int k) {
    int n = list->length / k;
    Position prev = list->head;
    Position head = list->head->next;
    Position nextPrev = NULL;
    for (int i = 0; i < n; i++) {
        prev->next = ReverseList(head, k, &nextPrev);
        // 现在 head 节点是逆转后的尾结点
        prev = head;
        // 考虑有尾巴不反转的情况
        head->next = nextPrev;
        head = nextPrev;
    }
}
